lib/Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/grafos/bellman.cpp

   1 struct edge{
   2   int u, v, w;
   3 };
   4
   5 edge * e; //e = Arreglo de todas las aristas
   6 long long d[300]; //Distancias
   7 int n; //Cantidad de nodos
   8 int m; //Cantidad de aristas
   9
  10 /*
  11   Retorna falso si hay un ciclo de costo negativo.
  12
  13   Si retorna verdadero, entonces d[i] contiene la distancia más corta entre el s y el nodo i.
  14  */
  15 bool bellman(int &s){
  16   //Llenar e
  17   e = new edge[n];
  18   //...
  19
  20   for (int i=0; i<n; ++i) d[i] = INT_MAX;
  21   d[s] = 0LL;
  22
  23   for (int i=0; i<n-1; ++i){
  24     bool cambio = false;
  25     for (int j=0; j<m; ++j){
  26       int u = e[j].u, v = e[j].v;
  27       long long w = e[j].w;
  28       if (d[u] + w < d[v]){
  29         d[v] = d[u] + w;
  30         cambio = true;
  31       }
  32     }
  33     if (!cambio) break; //Early-exit
  34   }
  35
  36   for (int j=0; j<m; ++j){
  37     int u = e[j].u, v = e[j].v;
  38     long long w = e[j].w;
  39     if (d[u] + w < d[v]) return false;
  40   }
  41
  42   delete [] e;
  43   return true;
  44 }